/** 可放入背包的物品 */
type Articles = {
    weight: number, // 物品的重量
    value: number, // 物品的价值
    quantity: number, // 物品的拥有数量
};
/**
 * 分数背包问题：0-1背包只能向背包里装入完整的物品，而分数背包问题是可以装入分数的物品。
 * @param capacity 背包容量
 * @param articles 各自带有重量、价值和数量的物品
 */
export function knapSackGreedy(capacity: number, articles: Articles[]) {
    // 总重量
    let load = 0;
    // 总价值
    let val = 0;
    // 遍历物品，当总重量达到背包容量就算完成
    for (let i = 0; i < articles.length && load < capacity; i++) {
        // 当前物品比剩余容量小，够放入
        if (articles[i].weight <= capacity - load) {
            val += articles[i].value;
            load += articles[i].weight;
            // console.log('using item ' + (i + 1) + ' for the solution');
        } else {
            // 不够的话就用分割一部分
            const r = (capacity - load) / articles[i].weight;
            val += r * articles[i].value;
            load += articles[i].weight;
            // console.log('using ratio of ' + r + ' for item ' + (i + 1) + ' for the solution');
        }
    }
    return val;
}
